package medium.recursion;

import java.util.ArrayList;
import java.util.List;

/**
 * <a href="https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number">17. 电话号码的字母组合</a>
 * 给定一个仅包含数字2-9的字符串，返回所有它能表示的字母组合。答案可以按任意顺序返回。
 * 给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
 * 示例 1：
 *   输入：digits = "23"
 *   输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
 * 示例 2：
 *   输入：digits = ""
 *   输出：[]
 * 示例 3：
 *   输入：digits = "2"
 *   输出：["a","b","c"]
 * 提示：
 *   0 <= digits.length <= 4
 *   digits[i] 是范围 ['2', '9'] 的一个数字。
 * 解题思路：
 *   1.使用递归方法，传入数字串以及拼接字符串，初始传入空字符串，递归结束条件为输入数字串不为空串
 *   2.取传入数字串的首个数字n，映射成字母数组里下标为n的子数组
 *   3.对子数组进行遍历，每次遍历都会取得一个字母，与拼接字符串拼接，作为下一个递归的入参
 *   4.排除数字串的第一个数字，剩余数字串也作为下一个递归的入参
 *   5.将步骤3和步骤4的结果作为递归方法的入参，执行递归
 *   6.当数字串为空时，表示已经递归到底了，可以将拼接字符串作为一个正确答案添加到答案list里
 * @author 刘学松
 * @date 2021/3/3 20:35
 */
public class 电话号码的字母组合 {
    String[][] letters = {{""},{""}, {"a", "b", "c"}, {"d", "e", "f"}, {"g", "h", "i"},
            {"j", "k", "l"}, {"m", "n", "o"}, {"p", "q", "r", "s"},
            {"t", "u", "v"}, {"w", "x", "y", "z"}};
    List<String> list = new ArrayList<>();

    public List<String> letterCombinations(String digits) {
        if (digits.length() == 0) {
            return list;
        }
        recursion(digits, "");
        return list;
    }

    public void recursion(String digits, String answer) {
        int length = digits.length();
        if (length > 0) {
            int digit = Integer.parseInt(digits.substring(0, 1));
            for (int i = 0; i < letters[digit].length; i++) {
                recursion(digits.substring(1, length), answer+letters[digit][i]);
            }
        } else {
            list.add(answer);
        }
    }
}
